I. Field of the Invention
The present invention relates to electronic memory. More particularly, the present invention relates to a novel and improved method for minimizing data relocation overhead in systems utilizing sectored EEPROM based files.
II. Description of the Related Art
Electronic memory of some type is used in almost all modern electronic devices. Electronic memory can take the form of floppy discs, magnetic tape, hard discs, and integrated chips (IC). Each form of memory has its advantages and disadvantages. Floppy discs allow numerous data updates on a portable medium but have limited capacity and long read and write access times. Both magnetic tape and hard discs have the capability for enormous capacity but are not portable, require large amounts of support hardware, and have slow read and write access times. IC memory is typically used where memory needs to be integrated into a portable device. Varying the type and number of ICs can scale the amount of memory. ICs require minimum support hardware, are extremely small, and can provide fast read and write access times.
Numerous different types of IC memory are available to provide solutions to various design requirements. Each type of memory is able to satisfy a number of design requirements, but no one memory type is able to provide a complete design solution. The type of memory chosen for any particular application will depend on planned usage and performance design trade-offs.
The most common type of IC memory is Read Only Memory (ROM). As the name implies, the memory is only read accessible. A ROM device cannot be written to once it has been programmed. Embedded software applications use ROM to store embedded code and look up tables. The processor in an embedded software application retrieves each instruction from ROM and executes it. Different types of ROM are available depending on the volatility of the information to be programmed within the ROM. If the information to be stored in ROM is not expected to change and the expected volume of devices is high then mask programmable ROM is used. This type of ROM is mask programmed prior to packaging of the die. The information to be programmed must be highly stable and not subject to revision since changes in the programmed information require a mask change. The benefits of using mask programmed ROM relate to cost and time savings for high volume, mature products. Other types of ROM are available for products that do not sustain production volumes or code stability sufficient to justify mask programmed ROM.
Programmable Read Only Memory (PROM) allows the device manufacturer to program the embedded code. This allows for revisions in the code but still does not allow for modification or erasure of the ROM once it has been programmed. Devices that have been programmed with an out of date code revision will either need to be used with the out of date code revision or will need to be discarded.
Erasable Programmable Read Only Memory (EPROM) provides the ability to completely erase a programmed part. Erasure of an EPROM is accomplished by exposing the die to ultraviolet (UV) light for a predetermined period of time. The die can be exposed to the UV light through a transparent window on the EPROM package. Once erased, the EPROM can be reprogrammed. EPROMs are typically only used for engineering development where the expected number of code revisions is high. The limitations on the package type that can accommodate the transparent window contribute to the much higher price of an EPROM when compared to a PROM. Although the EPROM can be erased and reprogrammed, modifications to the code must be done on a complete chip basis. Even changes to a single bit within the code require complete erasure and reprogramming. This limitation, along with the requirement for a UV light for erasure confine the task of updating EPROMs to original equipment manufacturers (OEMs).
A device that allows for selective content erasure and reprogramming is the Electrically Erasable Programmable Read Only Memory (EEPROM). Conventional EEPROM allows for data to be updated in place. That is, a particular data location can be erased and new data overwritten in the same location. Data can be read from an EEPROM quickly but the write cycle of the conventional EEPROM can be orders of magnitude longer than the read time. Another disadvantage of using a conventional EEPROM arises from the inherent structure of the conventional EEPROM cell. The structure of a conventional EEPROM cell requires more transistors than in a standard PROM. The increased structure results in reduced memory capacity and increased cost. These disadvantages make usage of conventional EEPROM prohibitive in most consumer electronics applications.
Random Access Memory (RAM) represents one alternate means for storage. RAM allows for selective data reads and writes. Read and write can be performed on a byte basis. No erase cycle is required before writing new data to a previously written byte. Moreover, unlike the EEPROM, the read and write cycle times of the RAM are nearly identical. The density and capacity of RAM is comparable to ROM. The major disadvantage in using RAM is the volatile nature of the stored data. Information stored in RAM is lost whenever the RAM powers down. This is in contrast to ROM, which is nonvolatile memory, where the contents of memory remain even after the IC has been power cycled. In order to retain the contents of RAM, power must be maintained on the chip at all times. This requires a battery back up to the normal power supply. If the battery back up fails when the power supply is de-energized the contents of RAM will be lost. For this reason RAM is not used for embedded code and is used only for dynamic memory. RAM used for embedded code would be susceptible to loss of battery power and power supply glitches. Furthermore, if RAM were used for embedded code, battery operated devices such as cellular telephones would have diminished battery life due to the constant power requirements of the RAM. When RAM is used for dynamic memory the system does not care if the contents are lost after a power cycle. This alleviates the need for battery back up.
Another storage alternative is sectored EEPROM commonly referred to as flash memory. Sectored EEPROM is a nonvolatile storage device that allows read and write on a byte basis. Unlike RAM, in sectored EEPROM an erase operation must be performed before rewriting over a previously written byte. However, data erasure cannot be performed on a byte basis. Erasure can only be performed on a sector basis, where the size of the sector is defined by the particular memory device chosen. The size of an erasable sector is always larger than one byte and can be on the order of 64 kbytes. However, the number of erase cycles is not unlimited, but is bounded by a maximum cycle life. A typical recommended erase cycle life for sectored EEPROM is 100,000 cycles. Therefore, one would not use sectored EEPROM for applications requiring greater than 100,000 erase cycles over the anticipated device lifetime. Sectored EEPROM has advantages over the other types of rewriteable memory in applications that require fewer than 100,000 erase and rewrite cycles. Sectored EEPROM is preferred over any type of RAM for embedded code applications because sectored EEPROM is nonvolatile. Sectored EEPROM is preferable over EPROM because of sectored EEPROM""s ability to rewrite portions of memory in circuit. Sectored EEPROM also does not require the UV light for chip erasure. Additionally, sectored EEPROM is preferable over conventional EEPROM, which has similar rewrite limitations, because of the lower cost and higher density of sectored EEPROM devices.
Because of the advantages of sectored EEPROM over other types of memory, sectored EEPROM is typically used for embedded code space storage in portable battery operated devices such as cellular telephones. Manufacturer programmed user specific data, such as phone ESN, service provider information, and phone number are also stored within sectored EEPROM. Other user specific data may be saved in sectored EEPROM if the expected number of update cycles does not exceed the maximum cycle life of the sectored EEPROM device. Other persistent data in the form of system data, data transmitted to wireless phones over the air, and user entered data may also require storage in nonvolatile memory. If persistent data is to be mapped to sectored EEPROM space, the expected updates over the lifetime of the unit must be relatively low and an efficient method of sectored EEPROM allocation for the new and updated data needs to be developed.
The present invention is a novel and improved method of allocating and updating data in sectored EEPROM. The method dynamically assigns data blocks within sectored EEPROM to minimize data relocation overhead when erasing portions of sectored EEPROM.
When a particular sectored EEPROM device is chosen for an application its manufacturer data sheet will define a sector as the minimum erasable size. A page or block of data is defined as the minimum relocatable data size for the information that is to be saved in sectored EEPROM. The size of a page or block must be less than the size of a sector but must be equal or greater than one byte. Ideally, a page size is defined to be large enough to define a control information portion and a data portion. The data portion of the block contains the actual file information. The control information portion contains information identifying the block as well as a block version number and a block relocation count. The block version number is a record of the number of times the particular block has been updated since its creation. The minimum value of the block version number is one, which signifies the contents of the block as the original data written to that location. The block relocation count is a record of the number of times a block has been relocated to allow a sector erase operation. The minimum value of the block relocation count is zero, which signifies the data in the block has never been relocated to allow a sector erase. A block volatility number is then calculated using the block version number and the block relocation count. (Note: Volatility used in this context relates to the dynamic quality of the data and does not refer to the memory""s ability to retain its contents after power cycle.) If block volatility is defined as v: v=(block version number+initial offset)/(block relocation count+1) Initial offset refers to a predetermined parameter controlling a block""s initial assigned volatility. An arithmetic average of all the block volatility numbers within each sector is calculated to achieve a sector average. When an erase cycle for a particular sector is initiated the sector will contain a mixture of valid and obsolete blocks. The valid blocks must be relocated to other locations in sectored EEPROM prior to the erase cycle or else they will be lost. The valid data blocks are relocated according to a relocation hierarchy. The hierarchy is determined using the calculated volatility of the valid memory block to be relocated, the average sector volatility, and the contents of the sector. When the block is relocated it is written to the lowest addressed block within the sector satisfying the relocation hierarchy. For each block to be relocated a volatility metric is calculated as | average sector volatilityxe2x80x94v|. First in the hierarchy is the most occupied sector containing no obsolete blocks where the volatility metric is less than a predetermined threshold. Next highest in the relocation hierarchy is the first available empty sector, followed by the sector containing the fewest obsolete blocks where the volatility metric is less than the predetermined threshold. Finally, if none of the other locations is available, the block is relocated to the sector containing the fewest obsolete blocks.